#include "BSTree.h"

#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#define MAX(A, B) ((A) > (B) ? (A) : (B))
/*
typedef struct BSTNode {
  void *data;
  struct BSTNode *lchild, *rchild;
} BSTNode;

typedef struct BSTree_t{
  BSTNode *root;
  size_t size;
} *BSTree;

typedef void (*trv_t)(void *);

typedef int (*cmpr_t)(void *, void *);

*/

int init_BST(BSTree *tr, size_t size) {
  (*tr) = malloc(sizeof(struct BSTree_t));
  if ((*tr) == NULL) {
    return -1;
  }
  (*tr)->root = NULL;
  (*tr)->size = size;
  return 1;
}

// 内部接口创建结点
static BSTNode *__new_node(const void *data, const size_t size) {
  BSTNode *new = malloc(sizeof(BSTNode));
  if (new == NULL) {
    return NULL;
  }

  memcpy(new->data, data, size);
  new->lchild = NULL;
  new->rchild = NULL;
  return new;
}

// 内部接口插入
static int __insert_node(struct BSTNode **root, const BSTNode *new_node,
                         const cmpr_t cmpr) {
  if ((*root) == NULL) {
    (*root) = (struct BSTNode *)new_node;
    return 0;
  }
  int ret = cmpr((*root)->data, new_node->data);
  if (ret >= 0) {
    return __insert_node(&(*root)->lchild, new_node, cmpr);
  } else {
    return __insert_node(&(*root)->rchild, new_node, cmpr);
  }
}

int push_BST(BSTree tr, const void *data, const cmpr_t cmpr) {
  if (tr == NULL || data == NULL) {
    return -1;
  }
  BSTNode *new = __new_node(data, tr->size);
  if (new == NULL) {
    return -1;
  }
  return __insert_node(&(tr->root), new, cmpr);
}

static struct BSTNode **__max_node(struct BSTNode **root) {
  if ((*root) == NULL) {
    return NULL;
  }
  if ((*root)->rchild == NULL) {
    return root;
  }
  return __max_node(&((*root)->rchild));
}

static int __delete(BSTree tr, struct BSTNode **root) {
  struct BSTNode *del = root;
  if (del->lchild == NULL) {
    (*root) = (*root)->rchild;
    free(del);
  } else if (del->rchild == NULL) {
    *root = del->lchild;
    free(del);
  } else {
    struct BSTNode **prev = __max_node(&(*root)->lchild);
    memcpy((*root)->data, (*prev)->data, tr->size);

    free(del);
  }
  return 0;
}

int pop_BST(BSTree tr, const void *data, const cmpr_t cmpr) {}

void *find_index_BST(const BSTree tr, const void *data, const cmpr_t cmpr);

int trave_BST(const BSTree tr, const trv_t trv);

int destory_BST(BSTree *tr);

int height(BSTNode *node) {
  if (node == NULL) {
    return 0;
  }
  return MAX(height(node->rchild), height(node->lchild)) + 1;
}
